#ifndef ANILLO_H_
#define ANILLO_H_

#include <iostream>
#include <cassert>
using namespace std;

//se puede asumir que el tipo T tiene constructor por copia
//y operator==
//no se puede asumir que el tipo T tenga operator=
template<typename T>
class Anillo {
public:

	/*
	 * constructor por defecto, crea un anillo
	 */
	Anillo();

	/*
	 * constructor por copia, una vez copiado, ambos anillos deben ser
	 * independientes, es decir, cuando se borre uno no debe morir el otro.
	 */
	Anillo(const Anillo<T>&);

	/*
	 * Destructor. Acordarse de liberar toda la memoria!
	 */
	~Anillo();

	/*
	 * Devuelve true si los anillos son iguales
	 */
	bool operator==(const Anillo<T>&) const;

	/*
	 * Dice si el anillo es vacío.
	 */
	bool esVacio() const;

	/*
	 * Dice el tamanio del anillo
	 */
	int tamanio() const;

	/*
	 * Devuelve el elemento actual del anillo
	 * PRE: no es vacío el anillo.
	 */
    const T& actual() const;

	/*
	 * Devuelve el próximo elemento según el orden del anillo.
	 * El anillo debe rotar. Con lo cual sucesivas llamadas a esta función
	 * retornan distintos valores.
	 *
	 * El valor retornado pasa a ser el anterior.
	 *
	 * PRE: no es vacío el anillo.
	 */
	const T& siguiente();
	
	/*
	 * Agrega el elemento al anillo. Recordar que el último agregado es el
	 * actual
	 */
	void agregar(const T&);

	/*
	 * Elimina una ocurrencia del elemento en el anillo.
	 */
	void eliminar(const T&);

	/*
	 * Marca el elemento actual.
	 *
	 * PRE: no es vacío el anillo.
	 */
    void marcar();

	/*
	 * Indica si algún del anillo está marcado.
	 */
	bool hayMarcado() const;

	/*
	 * Indica cuál es el elemento marcado la última vez.
	 *
	 * PRE: hayMarcado
	 */
	const T& marcado() const;

	/*
	 * Vuelve hacia atrás un elemento.
	 * El anterior, en caso de existir, no debe alterarse.
	 */
	void retroceder();

	/*
	 * debe mostrar el anillo en el stream (y retornar el mismo).
	 * Anillo vacio: []
	 * Anillo con 2 elementos (e1 es el actual): [e1, e2]
	 * Anillo con 2 elementos (e2 es el actual y e1 fue marcado): [e2, e1*]
	 * Anillo con 3 elementos (e3 es el actual, e2 fue agregado antes que e3, e1 fue agregado antes que e2): [e3, e2, e1]
	 *
	 */
	ostream& mostrarAnillo(ostream&) const;

private:
	//No se puede modificar esta funcion.
	Anillo<T>& operator=(const Anillo<T>& otro) {
		assert(false);
		return *this;
	}

	//Aca va la implementacion del nodo.
	struct Nodo {
		Nodo( const T &otro ) : dato(otro) {}
		Nodo *siguiente;
		Nodo *anterior;
		T dato;
	};
	
	Nodo *       m_actual;
	Nodo *       m_marcado;
	unsigned int m_tamanio;
};

template<typename T>
ostream& operator<<(ostream& out, const Anillo<T>& a) {
	return a.mostrarAnillo(out);
}

// implementación a hacer por los alumnos
template<typename T>
Anillo<T>::Anillo() {
	m_actual  = 0;
	m_marcado = 0;
	m_tamanio = 0;
}

template<typename T>
Anillo<T>::Anillo(const Anillo<T> &anillo) {
	m_tamanio = anillo.m_tamanio;

	if ( !m_tamanio ) {
		m_actual = m_marcado = NULL;
		return;
	}

	Nodo *primero = anillo.m_actual;
	Nodo *actual = primero;

	Nodo *copiaAnterior = NULL, *copia;
	m_actual = NULL;
	m_marcado = NULL;

	do {
		copia = new Nodo ( actual->dato );
		if ( !m_actual ) m_actual = copia;

		copia->anterior = copiaAnterior;

		if ( copiaAnterior )
			copiaAnterior->siguiente = copia;

		if ( anillo.m_marcado == actual )
			m_marcado = copia;

		actual = actual->siguiente;
		copiaAnterior = copia;
	} while ( actual != primero );

	copia->siguiente = m_actual;
	m_actual->anterior = copia;
}

template<typename T>
Anillo<T>::~Anillo() {
	Nodo *t_actual = m_actual;
	
	for(unsigned int i = 0; i < m_tamanio; i++) {
		Nodo *temp = t_actual;
		t_actual   = t_actual->siguiente;
		
		delete temp;
	}
	
	m_actual  = 0;
	m_tamanio = 0;
	m_marcado = 0;
}

template<typename T>
bool Anillo<T>::esVacio() const {
	return m_tamanio == 0;
}

template<typename T>
int Anillo<T>::tamanio() const {
	return m_tamanio;
}

template<typename T>
const T& Anillo<T>::actual() const {
	return m_actual->dato;
}

template<typename T>
const T& Anillo<T>::siguiente() {
	// Nos guardamos un puntero temporal al actual
	Nodo *anterior = m_actual;
	
	// Pasamos al siguiente en el anillo
	m_actual = m_actual->siguiente;
	
	// Devolvemos el anterior
	return anterior->dato;
}

template<typename T>
void Anillo<T>::agregar(const T &elem) {
	// Creamos el nuevo nodo
	Nodo *nuevo = new Nodo( elem );
	
	if(m_actual != 0) {
		// Si el anillo no está vacío entonces ponemos
		// el nuevo nodo adelante del actual
		nuevo->siguiente = m_actual;
		nuevo->anterior  = m_actual->anterior;
		
		nuevo->anterior->siguiente = nuevo;
		nuevo->siguiente->anterior = nuevo;
	} else {
		// Si el anillo está vacío entonces el nuevo
		// nodo será el único en la lista
		nuevo->siguiente = nuevo;
		nuevo->anterior  = nuevo;
	}
	
	// actual ahora apunta al nuevo nodo
	m_actual = nuevo;
	m_tamanio++;
}

template<typename T>
void Anillo<T>::eliminar(const T &elem) {
	Nodo *t_actual = m_actual;
	
	do {
		// Si encontramos el elemento a eleminar
		if(t_actual->dato == elem) {
			if(m_tamanio > 1) {
				t_actual->siguiente->anterior = t_actual->anterior;
				t_actual->anterior->siguiente = t_actual->siguiente;
			}
			
			if(t_actual == m_actual)
				m_actual = m_tamanio > 1 ? m_actual->siguiente : 0;
			
			if(t_actual == m_marcado)
				m_marcado = 0;
			
			delete t_actual;
			m_tamanio--;
			
			break;
		}
		
		t_actual = t_actual->siguiente;
	} while(t_actual != m_actual);
}

template<typename T>
void Anillo<T>::marcar() {
	m_marcado = m_actual;
}

template<typename T>
bool Anillo<T>::hayMarcado() const {
	return m_marcado != 0;
}

template<typename T>
const T& Anillo<T>::marcado() const {
	return m_marcado->dato;
}

template<typename T>
void Anillo<T>::retroceder() {
	m_actual = m_actual->anterior;
}

template<typename T>
ostream& Anillo<T>::mostrarAnillo(ostream &salida) const {
	salida << "[";
	
	Nodo *t_actual = m_actual;
	for(unsigned int i = 0; i < m_tamanio; i++) {
		salida << t_actual->dato;
		
		if(t_actual == m_marcado)
			salida << "*";
		
		if(i < m_tamanio - 1)
			salida << ", ";
		
		t_actual = t_actual->siguiente;
	}
	
	salida << "]";
	return salida;
}

template<typename T>
bool Anillo<T>::operator==( const Anillo<T> &otro ) const {
	if ( m_tamanio != otro.m_tamanio ) return false;
	if ( !m_tamanio ) return true;

	Nodo *actualLeft = m_actual,
		*primeroLeft = m_actual,
		*actualRight = otro.m_actual;

	do {
		if ( actualLeft->dato != actualRight->dato )
			return false;

		// Si está el elemento marcado en cualquiera de los anillos...
		if ( m_marcado == actualLeft || otro.m_marcado == actualRight ) {
			// Pero está marcado sólo en uno...
			if ( m_marcado != actualLeft || otro.m_marcado != actualRight )
				return false;
		}

		actualLeft = actualLeft->siguiente;
		actualRight = actualRight->siguiente;
	} while( actualLeft != primeroLeft );

	return true;
}

#endif //ANILLO_H_
